//
// Created by Lenovo on 2021/5/27.
//

#include <iostream>
#include "city.h"
#include "Floyd.h"
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;
const int INF = 1e9+10;
struct node{
    int nl = 0;
    int lb = 0;
    int now_city;
    int aim_city;
    vector<int>visited_city;
    bool find_city(int id){
        for(auto it:visited_city){
            if(it==id) return 1;
        }
        return 0;
    }
    void print(){
        for(auto it:visited_city) cout<<it;
        cout<<endl;
    }
    friend bool operator <(const node& a,const node& b){
        return (a.lb+a.nl)>(b.lb+b.nl);
    }
};
priority_queue<node>pq;
int mp[maxn][maxn];
int route[maxn];
City city;
Floyd fl;
class TSP
{
public:

    void init(){
        city.updata(INF,INF);
        city.inputcity_num();
        int num = city.getcity_num();
        //fl.build_grahp(num);
        //fl.build_mp();
        //fl.floyd(num);
        ifstream fd;
        fd.open("C:\\Users\\Lenovo\\Desktop\\TSP\\tsp10.txt");
        if(!fd.is_open()) {
            puts("error");
            return;
        }
        int x;
        for(int i = 1;i<=num;i++){
            for(int j = 1;j<=num;j++) {
                fd>>x;
                mp[i][j] = x;
            }
        }
        fd.close();
    }
    void solve(){
        //cout<<"*******"<<endl;
        node nw;
        for(int i = 1;i<=city.getcity_num();i++){
            int minn = INF;
            for(int j = 1;j<=city.getcity_num();j++){
                minn = min(minn,mp[i][j]);
            }
            nw.lb+=minn;
            route[i] = minn;
        }
        nw.visited_city.push_back(1);
        nw.now_city = 1;
        nw.aim_city = 1;
        pq.push(nw);
        while(!pq.empty()){
            node n_state = pq.top();
            pq.pop();
            if(n_state.visited_city.size()==city.getcity_num()){
                city.updata(n_state.lb,n_state.nl+mp[n_state.now_city][n_state.aim_city]);
            }
            else{
                node tmp;
                for(int i = 1;i<=city.getcity_num();i++){
                    if(!n_state.find_city(i)){
                        tmp = n_state;
                        tmp.now_city = i;
                        tmp.visited_city.push_back(i);
                        tmp.nl += mp[n_state.now_city][tmp.now_city];
                        tmp.lb -= route[tmp.visited_city.size()];
                        if(tmp.nl<city.get_upweight()) pq.push(tmp);
                    }
                }
            }
        }
        cout<<city.get_upweight()<<endl;
    }
};
